1. Field of the Invention
This invention relates to cryptographic systems, and more specifically to systems including public key digital signatures.
2. Description of Prior Art
By now the potential of the public key digital signature in commercial applications of cryptography is widely appreciated. A system using such signatures, called blind signatures, is presented in the co-pending application of the same applicant, U.S. application Ser. No. 524,896 and European Patent Application No. 84201160.3 published as publication No. 0139313A2 on May 2, 1985, which are included herein by reference. The present application relates to a novel blind signature system, as will be presented.
In an RSA public key signature system, a party who may be called the signer chooses two appropriate large primes p and q, and makes their product n (=p.multidot.q) public. The signer also makes public one or more public exponents e.sub.1, . . . , e.sub.i. Additionally the signer computes corresponding secret exponents d.sub.1, . . . , d.sub.i satisfying d.sub.i .ident.e.sub.i.sup.-1 (mod(p-1).multidot.(q-1)). The signer forms the ith signature on a number m as m'.sub.i .ident.m.sup.d.sbsp.i (mod n). Anyone can use the public n and e.sub.i to verify the signature on m by checking that m.ident.(m'.sub.i).sup.e.sbsp.i (mod n) holds.
The blind signature concept recognizes the utility of keeping the signer performing a commercial service, such as validating electronic bank notes, notarizing or time stamping electronic documents, etc., from determining the exact content of each message signed. The essential concept of the preferred embodiments of the co-pending application mentioned is that a party wishing a signature on some message first blinds the message before submitting it to the signer for the signature, and then is able to unblind the signed message received from the signer to recover the original message bearing the signature. In a preferred embodiment of the already mentioned application, the blinding of a message m with a random r produces t.ident.m.multidot.r.sup.e.sbsp.i (mod n), the signing of t yields t'.ident.m.sup.d.sbsp.i .multidot.r(mod n), and the provider unblinds t' by forming m'.sub.i .ident.t'.multidot.r.sup.-1 (mod n), yielding m'.sub.i .ident.m.sup.d.sbsp.i (mod n).
Notice that it is necessary for the provider to anticipate the particular d.sub.i to be used by the signer. Its is possible, though computationally expensive, for the provider to anticipate a few possible d.sub.i by forming t.ident.m.multidot.r.sup.e.sbsp.1.sup.e.sbsp.2 (mod n) for example, and being able to unblind in case of signature with d.sub.1 or d.sub.2 by forming m'.sub.1 .ident.(m.multidot.r.sup.e.sbsp.1.sup.e.sbsp.2).sup.d.sbsp.1 .multidot.r.sup.-e.sbsp.2 (mod n) or m'.sub.2 .ident.(m.multidot.r.sup.e.sbsp.1.sup.e.sbsp.2).sup.d.sbsp.2 .multidot.r.sup.-e.sbsp.1 (mod n), depending on whether d.sub.1 or d.sub.2 was used to sign, respectively. But such an approach becomes prohibitively computation intensive as the number of alternatives increases, in general requiring the provider to perform more than one multiplication for each alternative anticipated, since each e.sub.i should have a unique prime factor otherwise some signatures can be made from others. Such effort required to anticipate all possible signatures may not be practical, and is also undesirable because the maximal extent of a system has to be fixed initially and effort required for the maximal extent has to be carried out from the beginning. Of course such an approach becomes impossible in practice when the number of alternatives is large or when the alternatives are not known in advance of the blinding transformation.
Even the simple payments system mentioned in the co-pending application has advantage in the bank's customer supplying a large number of blinded items when an account is opened, without the customer knowing in advance the particular choice of signature, which the bank will use to encode the denomination and possibly other data when it ultimately issues the notes. Additionally, improved security in some protocols can result if the parties must fix certain parameters before the kind of signatures to be used are revealed. It is anticipated that many other uses of blind signatures may find considerable advantage if not practical necessity in systems not requiring the kind of signature(s) to be anticipated in advance of blinding.